#include <bits/stdc++.h>
using namespace std;

/*
386. 字典序排数
已解答
中等
相关标签
premium lock icon
相关企业
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

 

示例 1：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：

输入：n = 2
输出：[1,2]
 

提示：

1 <= n <= 5 * 104
*/


// 法一
// 字典树遍历 迭代形式  模拟DFS
class Solution {
public:
    vector<int> lexicalOrder(int n) {
        // 字典树遍历 迭代形式  模拟DFS
        vector<int> ans;
        stack<int> sta;
        for (int i = 9; i >= 1; --i) {
            if (i <= n)     sta.push(i);
        }
        // 模拟栈
        while (!sta.empty()) {
            int x = sta.top();
            sta.pop();
            ans.push_back(x);
            for (int i = 9; i >= 0; --i) {
                int next = x * 10 + i;
                if (next <= n)     sta.push(next);
            }
        }
        return ans;
    }
};

// 法二
// DFS 字典树法（递归）
class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res;
        for (int i = 1; i <= 9; ++i) {
            dfs(i, n, res);
        }
        return res;
    }

    void dfs(int x, int n, vector<int>& res) {
        if (x > n) return;
        res.push_back(x);
        for (int i = 0; i <= 9; ++i) {
            dfs(x * 10 + i, n, res);
        }
    }
};

// 法三 数学公式推导
// 从 curr=1 开始，每次尝试 curr *= 10（优先深度遍历）。
// 如果 curr > n，则回退 curr /= 10 并 ++curr，跳过末尾的 0（如 19 的下一个是 2，不是 20）。

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res(n);
        int curr = 1;
        for (int i = 0; i < n; ++i) {
            res[i] = curr;
            if (curr * 10 <= n) {
                curr *= 10;  // 优先深度遍历（1→10→100）
            } else {
                if (curr >= n) curr /= 10;  // 回退（如 13→1）
                curr++;
                while (curr % 10 == 0) curr /= 10;  // 跳过末尾0（19→2）
            }
        }
        return res;
    }
};